This disclosure relates to program analysis, and more particularly, to a hybrid program analysis.
The process of program analysis may generally be divided into two groups, static program analysis and dynamic program analysis. In static program analysis, an analysis of computer software may be performed without executing the application being analyzed. In dynamic program analysis, the application is executed on a real or virtual processor using test inputs during an analysis.
Static program analysis is generally considered undecidable according to Rice's theorem. Rice's theorem states that, for any non-trivial property of partial functions, there is no general and effective method to determine whether an algorithm determines a partial function with that property. Rice's theorem not only provides a theoretical upper bound, but also a limitation that's encountered by many analyses of practical interest.
Among these undecidable analyses are the problem of determining a precise set of called methods for a given call site (also known as pointer analysis) is undecidable, the problem of resolving reflective calls is undecidable, and problems related to string analysis and constant propagation.
Sound solutions for the above problems typically suffer from poor precision. For example, the result of a call (in Java) to Class.newInstance can be approximated as all possible types in the class hierarchy of the subject application. However, the approximation of the result yields an imprecise and un-scalable analysis.
An improved technique has been introduced to perform a two-stage analysis, where a dynamic program analysis is first run to determine dynamic hints for an ensuing static analysis, which may then use the dynamic hints for modeling of challenging code constructs. For example, in the case of Class.newInstance, the dynamic analysis records the exact types of objects allocated by the newInstance call, and then the static program analysis may use this data for pointer analysis to resolve virtual calls. While it is generally understood that such reliance on dynamic program analysis is unsound, the problems targeted by the two-stage analysis are undecidable and sound approximate solutions are often prohibitive in their loss of precision. That is, the two-stage analysis is merely an improved compromise as compared to static program analysis.